{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    return n * f(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6689502913449127057588118054090372586752746333138029810295671352301633557244962989366874165271984981308157637893214090552534408589408121859898481114389650005964960521256960000000000000000000000000000"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(120)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。\n",
    "\n",
    "使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。可以试试fact(1000)："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded in comparison",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-5-e53e357bdaba>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m10000\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-1-2da880fedd0f>\u001b[0m in \u001b[0;36mf\u001b[1;34m(n)\u001b[0m\n\u001b[0;32m      2\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0mn\u001b[0m \u001b[1;33m*\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[1;32m<ipython-input-1-2da880fedd0f>\u001b[0m in \u001b[0;36mf\u001b[1;34m(n)\u001b[0m\n\u001b[0;32m      2\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0mn\u001b[0m \u001b[1;33m*\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mRecursionError\u001b[0m: maximum recursion depth exceeded in comparison"
     ]
    }
   ],
   "source": [
    "f(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。\n",
    "\n",
    "尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。\n",
    "\n",
    "上面的fact(n)函数由于return n * fact(n - 1)引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fact(n):\n",
    "    return fact_iter(n, 1)\n",
    "\n",
    "def fact_iter(num, product):\n",
    "    if num == 1:\n",
    "        return product\n",
    "    return fact_iter(num - 1, num * product)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。\n",
    "\n",
    "针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。\n",
    "\n",
    "Python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 练习\n",
    "\n",
    "汉诺塔的移动可以用递归函数非常简单地实现。\n",
    "\n",
    "请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法，例如：\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 汉诺塔问题\n",
    "- 规则:\n",
    "    1. 每次移动一个盘子\n",
    "    2. 任何时候大盘子在下面，小盘子在上面\n",
    "- 方法: \n",
    "\n",
    "    n=1:  \n",
    "        直接把A上的一个盘子移动到C上， A->C\n",
    "    n=2: \n",
    "        把小盘子从A放到B上， A->B\n",
    "        把大盘子从A放到C上， A->C\n",
    "        把小盘子从B放到C上， B->C\n",
    "    n=3:\n",
    "        把A上的两个盘子，通过C移动到B上去， 调用递归实现\n",
    "        把A上剩下的一个最大盘子移动到C上， A->C\n",
    "        把B上两个盘子，借助于A，挪到C上去， 调用递归\n",
    "    n = n：\n",
    "        把A上的n-1个盘子，借助于C，移动到B上去，调用递归\n",
    "        把A上的最大盘子，也是唯一一个，移动到C上，A->C\n",
    "        把B上n-1个盘子，借助于A，移动到C上， 调用递归\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A --> C\n",
      "A --> B\n",
      "C --> B\n",
      "A --> C\n",
      "B --> A\n",
      "B --> C\n",
      "A --> C\n"
     ]
    }
   ],
   "source": [
    "def move(n, a, b, c):\n",
    "    '''\n",
    "    汉诺塔的递归实现\n",
    "    n：代表几个盘子\n",
    "    a：代表第一个塔，开始的塔\n",
    "    b：代表第二个塔，中间过渡的塔\n",
    "    c：代表第三个塔, 目标塔\n",
    "    '''\n",
    "    if n == 1:\n",
    "        print(a, \"-->\", c)\n",
    "        return None\n",
    "    '''\n",
    "    \n",
    "    if n == 2:\n",
    "        print(a, \"-->\", b)\n",
    "        print(a, \"-->\", c)\n",
    "        print(b, \"-->\", c)\n",
    "        return None\n",
    "    '''\n",
    "    # 把n-1个盘子，从a塔借助于c塔，挪到b塔上去\n",
    "    move(n-1, a, c, b)\n",
    "    print(a, \"-->\", c)\n",
    "    # 把n-1个盘子，从b塔，借助于a塔，挪到c塔上去\n",
    "    move(n-1,b, a, c)\n",
    "    \n",
    "a = \"A\"\n",
    "b = \"B\"\n",
    "c = \"C\"\n",
    "\n",
    "n = 3 \n",
    "move(n, a, b, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
